package com.atguigu.practice;

public class sortList {
    public static ListNode sort(ListNode head){
        return sort(head,null);
    }
    public static ListNode sort(ListNode head,ListNode tail){
        if(head==null){
            return null;
        }
        if(head.next==tail){
            head.next=null;
            return head;
        }
        ListNode slow=head; //慢指针
        ListNode fast=head; //快指针
        while (fast!=tail){
            slow=slow.next;
            fast=fast.next;
            if(fast!=tail){
                fast=fast.next;
            }
        }
        ListNode mid=slow;
        ListNode list1=sort(head,mid);
        ListNode list2=sort(mid,tail);
        ListNode node=merge(list1,list2);
        return node;
    }
    public static ListNode merge(ListNode l1,ListNode l2){
        return null;
    }
    public static void main(String[] args){

    }
}
